home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 19 / CU Amiga Magazine's Super CD-ROM 19 (1998)(EMAP Images)(GB)[!][issue 1998-02].iso / CUCD / Programming / LEDA / source / src / graph_alg / _dijkstra.c < prev    next >
Encoding:
C/C++ Source or Header  |  1994-11-16  |  2.7 KB  |  68 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  3.1c
  4. +
  5. +
  6. +  _dijkstra.c
  7. +
  8. +
  9. +  Copyright (c) 1994  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16.  
  17. /*******************************************************************************
  18. *                                                                              *
  19. *  DIJKSTRA  (single source shortest paths)                                    *
  20. *                                                                              *
  21. *******************************************************************************/
  22.  
  23.  
  24. #include <LEDA/graph_alg.h>
  25. #include <LEDA/node_pq.h>
  26.  
  27.  
  28. void DIJKSTRA(const graph& G, node s, const edge_array<num_type>& cost,
  29.                                             node_array<num_type>& dist,
  30.                                             node_array<edge>& pred )
  31. { /* 
  32.      computes single source shortest paths from node s for 
  33.      a non-negative network (G,cost), computes for all nodes v:
  34.      a) dist[v] = cost of shortest path from s to v
  35.      b) pred[v] = predecessor edge of v in shortest paths tree
  36.   */
  37.  
  38.   node_pq<num_type>  PQ(G);
  39.   node v;                                                                    
  40.   edge e;                                                                      
  41.                                                                                
  42.   forall_nodes(v,G)                                                            
  43.   { pred[v] = nil;                                                             
  44.     dist[v] = max_num;                                                      
  45.    }                                                                         
  46.  
  47.   dist[s] = 0;
  48.   PQ.insert(s,0);
  49.                                                                                
  50.   while (! PQ.empty())
  51.   { node u = PQ.del_min();
  52.     num_type du = dist[u];
  53.     forall_adj_edges(e,u)                                                    
  54.     { v = target(e);                                                      
  55.       num_type c = du + cost[e];                                              
  56.       if (c < dist[v])                                                    
  57.       { if (dist[v] == max_num) 
  58.            PQ.insert(v,c);
  59.         else 
  60.            PQ.decrease_inf(v,c);
  61.         dist[v] = c;                                                     
  62.         pred[v] = e;                                                     
  63.        }                                                                 
  64.      }                                                                    
  65.    } 
  66. }
  67.  
  68.